package cn.ac.istic.lkt.atv;

import java.util.ArrayList;
import java.util.List;
import java.util.Vector;

public class ParseTree {
	private String ptString;
	private List<PTNode> nodeList;
	private int depth=-1;
	private String sent;

	class StackNode{
		public int id;
		public int depth;
		public StackNode(int id, int d){
			this.id = id;
			this.depth = d;
		}
	}
	
	public ParseTree(String s){
		ptString = s;		
		nodeList = new ArrayList<PTNode>();
		parse();
		toSentence();
	}
	
	public int parse(){
		
		int slen = ptString.length();
		int lbc = 0; //left bracket number
		int rbc = 0; //right bracket number		
		for(int i=0; i<slen; i++){
			if (ptString.charAt(i) == '('){
				lbc ++;
			}
			if (ptString.charAt(i) == ')'){
				rbc ++;
			}
		}
		if(lbc != rbc){
			System.err.print("错误：输入树串的括号树目不匹配！");
			return -1;
		}
		
		int cdep=0;
		int j=0;
		Vector<StackNode> sn = new Vector<StackNode>();
		int pos_in_sen=0; //词在句子中的位置.
		
		for ( int i=0; i< slen; i++){
			if ( ptString.charAt(i) == '('){
				if( j==0 ){
					j = i+1;
				}
				else{
					String lb = ptString.substring(j,i);
					if (lb.trim().length() !=0 ){
						PTNode nt = new PTNode(nodeList.size(),lb.trim(),cdep,PTNode.NT);
						nodeList.add(nt);
						sn.add(new StackNode(nt.getID(),cdep));
						
					}
					/*
					else if( cdep > 0){
						System.err.print("Label is none, depth: "+ cdep+"\n");
						return -1;
					}*/
					cdep ++;
					j = i+1;
				}				
			}
			if ( ptString.charAt(i) == ')'){
				String lb = ptString.substring(j,i).trim();
				if (lb.contains(" ")){
					String[] slw = lb.split(" ");
					if (slw.length != 2){
						System.err.print(lb);
						return -1;
					}
					PTNode pos = new PTNode(nodeList.size(),slw[0],cdep,PTNode.POS);
					nodeList.add(pos);
					PTNode wd = new PTNode(nodeList.size(),slw[1],cdep+1,PTNode.WD);
					wd.setPos(pos_in_sen);
					pos_in_sen++;
					nodeList.add(wd);
					pos.setChild(wd.getID());
					wd.setParent(pos.getID());
					sn.add(new StackNode(pos.getID(),cdep));
				}
				else{
					if (sn.size() <=1){
						break;
					}
					StackNode fnode = sn.remove(sn.size()-1);
					while (sn.size()>0){
						StackNode bnode = sn.lastElement();
						if (bnode.depth < fnode.depth){
							nodeList.get(bnode.id).setChild(fnode.id);
							nodeList.get(fnode.id).setParent(bnode.id);	
							break;
						}
						else{							
							nodeList.get(bnode.id).setBrother(fnode.id);							
							fnode = sn.remove(sn.size() -1);
						}//if					
					}//while					
				}//else
				j = i + 1;
				cdep--;
			}//if
		}//for
		
		getHeight(0);
		for (int i=0; i<nodeList.size(); i++){
			int noded=nodeList.get(i).getDepth();
			if (depth <noded) depth=noded;
		}
		return 1;
	}
	
	public int getHeight(int id){
		int childid=nodeList.get(id).getChild();
		if (childid < 0) {
			nodeList.get(id).setHeight(0);
			return 0;
		}
		else{
			Vector<Integer> allc = new Vector<Integer>();
			allc.add(childid);
			while (true) {
				int newid = nodeList.get(childid).getBrother();
				if (newid >=0) {
					allc.add(newid);	
					childid=newid;
				}				
				else break;
			}
			int maxheight = 0;
			for (int i=0; i<allc.size(); i++){
				int height = getHeight((Integer)allc.get(i));
				if (height>maxheight) maxheight = height;				
			}
			nodeList.get(id).setHeight(maxheight+1);
			return maxheight + 1;
		}		
	}
	public List<PTNode> getTree(){
		return nodeList;
	}
	public int[] getChildren(int n){
		if(nodeList.get(n).isLeafNode()){
			return null;
		}
		
		ArrayList<Integer> children = new ArrayList<Integer>();;
		int firstc = nodeList.get(n).getChild();
		children.add(firstc);
		while (firstc > 0){
			firstc=nodeList.get(firstc).getBrother();
			if (firstc>=0) children.add(firstc);
		}
		int[] a = new int[children.size()];
		for (int i=0; i<children.size(); i++){
			a[i]=children.get(i);
		}
		return a;
	}
	public void toSentence(){
		StringBuffer sb = new StringBuffer();
		for (int i=0; i< nodeList.size(); i++){
			if(nodeList.get(i).isLeafNode()){
				sb.append(nodeList.get(i).getLabel()+" ");
			}
		}
		//System.out.println(sb.toString().trim());
		this.sent = sb.toString().trim();
	}
	
	public String toString(){
		String s="ID\tLabel\tParent\tChild\tBrother\tDepth\tHeight\tType\tPos_in_sen\n";
		for (int i =0; i< nodeList.size(); i++){
			s += nodeList.get(i).toString()+"\n";
		}
		return s;
	}
	public int getDepth(){
		return depth;
	}
	public String getSent() {
		return sent;
	}

	public void setSent(String sent) {
		this.sent = sent;
	}

	public static void main(String[] args) {
		ParseTree pt = new ParseTree("( (IP-HLN (NP-SBJ (NP-PN (NR 上海) (NR 浦东))  (NP (NN 开发) (CC 与) (NN 法制) (NN 建设))) (VP (VV 同步))) ) ");
		//pt.parse();
		// TODO Auto-generated method stub
		System.out.print(pt.toString());
	}
}
